package main.剑指OfferⅠ;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Day27 {
    public static void main(String[] args) {
        System.out.println("剑指Offer59-Ⅰ.滑动窗口的最大值");
        System.out.println("剑指Offer59-Ⅱ.队列的最大值");
    }
}

class Offer59_Ⅰ{
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        int left=0,right=0;
        while (right<k){
            while (!queue.isEmpty()&&nums[right]>queue.peekLast()) queue.pollLast();
            queue.addLast(nums[right]);
            right++;
        }
        list.add(queue.peekFirst());
        while (right< nums.length){
            int outNum=nums[left],inNum=Integer.MIN_VALUE;
            if (outNum==queue.peekFirst()) queue.pollFirst();
            inNum=nums[right];
            while (!queue.isEmpty()&&inNum>queue.peekLast()) queue.pollLast();
            queue.addLast(inNum);
            list.add(queue.peekFirst());
            left++;
            right++;
        }
        int[] result=new int[list.size()];
        for (int i=0;i<list.size();i++) result[i]=list.get(i);
        System.out.println(list);
        return result;
    }
}

class Offer59_Ⅱ{
    Deque<Integer> mainQueue,assistQueue;
    public Offer59_Ⅱ() {
        mainQueue=new LinkedList<>();
        assistQueue=new LinkedList<>();
    }

    public int max_value() {
        return assistQueue.isEmpty() ? -1 : assistQueue.peekFirst();
    }

    public void push_back(int value) {
        mainQueue.addLast(value);
        while (!assistQueue.isEmpty()&&value>assistQueue.peekLast()){
            assistQueue.pollLast();
        }
        assistQueue.addLast(value);
    }

    public int pop_front() {
        int value= mainQueue.isEmpty() ? -1 : mainQueue.pollFirst();
        if (!assistQueue.isEmpty()&&value==assistQueue.peekFirst()) assistQueue.pollFirst();
        return value;
    }
}